home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / stringsearch / bmsource / uf.om.md2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-05-06  |  3.1 KB  |  156 lines  |  [TEXT/MPS ]
  1. /*
  2.     search routine generated by gen.
  3.     skip=uf, match=om (using omr), shift=md2
  4. */
  5. #include    "freq.h"
  6. /*
  7.  * The authors of this software are Andrew Hume and Daniel Sunday.
  8.  * 
  9.  * Copyright (c) 1991 by AT&T and Daniel Sunday.
  10.  * 
  11.  * Permission to use, copy, modify, and distribute this software for any
  12.  * purpose without fee is hereby granted, provided that this entire notice
  13.  * is included in all copies of any software which is or includes a copy
  14.  * or modification of this software and in all copies of the supporting
  15.  * documentation for such software.
  16.  * 
  17.  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
  19.  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  20.  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  21.  */
  22.  
  23. #ifndef    CHARTYPE
  24. #define    CHARTYPE    unsigned char
  25. #endif
  26. #define    MAXPAT    256
  27.  
  28. static struct om
  29. {
  30.     int loc;
  31.     CHARTYPE c;
  32. };
  33.  
  34. om_pcmp(p1, p2)
  35.     register struct om *p1, *p2;
  36. {
  37.     register float f = freq[p1->c] - freq[p2->c];
  38.  
  39.     if(f < 0)
  40.         return(-1);
  41.     else if(f > 0)
  42.         return(1);
  43.     return(p2->loc - p1->loc);
  44. }
  45. #include    "stats.h"
  46.  
  47. #ifndef    TABTYPE
  48. #define    TABTYPE    long
  49. #endif
  50. typedef TABTYPE Tab;
  51.  
  52. static struct
  53. {
  54.     int patlen;
  55.     CHARTYPE pat[MAXPAT];
  56.     Tab delta[256];
  57.     struct om om[1024];
  58.     int nom;
  59.     int md2;
  60. } pat;
  61.  
  62. prep(base, m)
  63.     CHARTYPE *base;
  64.     register m;
  65. {
  66.     CHARTYPE *skipc;
  67.     register CHARTYPE *pe, *p;
  68.     register int j;
  69.     register Tab *d;
  70.     register struct om *op;
  71.     register CHARTYPE *opb, *ope;
  72.     register CHARTYPE *pmd2;
  73.  
  74.     pat.patlen = m;
  75.     if(m > MAXPAT)
  76.         abort();
  77.     memcpy(pat.pat, base, m);
  78.     skipc = 0;
  79.     stats.len = m;
  80.     d = pat.delta;
  81.     for(j = 0; j < 256; j++)
  82.         d[j] = pat.patlen;
  83.     for(p = pat.pat, pe = p+m-1; p < pe; p++)
  84.         d[*p] = pe-p;
  85.     d[*p] = 0;
  86.     skipc = (CHARTYPE *)p;
  87.     for(op = pat.om, opb = pat.pat, ope = opb+m-1; opb < ope; opb++){
  88.         op->loc = opb - ope;
  89.         op->c = *opb;
  90.         op++;
  91.     }
  92.     qsort(pat.om, pat.nom = op-pat.om, sizeof(pat.om[0]), om_pcmp);
  93.     for(pmd2 = skipc-1; pmd2 >= pat.pat; pmd2--)
  94.         if (*pmd2 == *skipc) break;
  95.     pat.md2 = skipc - pmd2;    /* *pmd2 is first leftward reoccurance of *pe */
  96. #ifdef    STATS
  97.     stats.extra += pat.md2;
  98. #endif
  99. }
  100.  
  101. exec(base, n)
  102.     CHARTYPE *base;
  103. {
  104.     int nmatch = 0;
  105.     register CHARTYPE *e, *s;
  106.     register Tab *d0 = pat.delta;
  107.     register k;
  108.     register struct om *op, *oep;
  109.     register md2 = pat.md2;
  110.  
  111.     s = base+pat.patlen-1;
  112.     e = base+n;
  113.     memset(e, pat.pat[pat.patlen-1], pat.patlen);
  114.     oep = pat.om+pat.nom;
  115.     while(s < e){
  116. #ifdef    STATS
  117.         k = d0[*s];
  118.         stats.jump++;
  119.         while(k){
  120.             stats.jump++; stats.step[k]++;
  121.             k = d0[*(s += k)];
  122.             stats.jump++; stats.step[k]++;
  123.             k = d0[*(s += k)];
  124.             stats.jump++; stats.step[k]++;
  125.             k = d0[*(s += k)];
  126.         }
  127. #else
  128.         k = d0[*s];
  129.         while(k){
  130.             k = d0[*(s += k)];
  131.             k = d0[*(s += k)];
  132.             k = d0[*(s += k)];
  133.         }
  134. #endif
  135.         if(s >= e)
  136.             break;
  137. #ifdef    STATS
  138.         stats.slow++;
  139. #endif
  140.         for(op = pat.om; op < oep; ++op){
  141. #ifdef    STATS
  142.             stats.cmp++;
  143. #endif
  144.             if(op->c != s[op->loc])
  145.                 goto mismatch;
  146.         }
  147.         nmatch++;
  148.     mismatch:
  149. #ifdef    STATS
  150.         stats.step[md2]++; stats.jump++;
  151. #endif
  152.         s += md2;
  153.     }
  154.     return(nmatch);
  155. }
  156.